package hot100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class Solution139 {
    private boolean ans;
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        dfs(s, 0, 0, set);
        return ans;
    }

    private void dfs(String s, int start, int end, Set<String> wordDict) {
        if (start == end && end == s.length()) {
            ans = true;
            return;
        }
        if (start > end || end >= s.length()) {
            return;
        }
        if (wordDict.contains(s.substring(start, end + 1))) {
            dfs(s, end + 1, end + 1, wordDict);
        }
        dfs(s, start, end + 1, wordDict);
    }

    public static void main(String[] args) {
        Solution139 solution139 = new Solution139();
        List<String> wordDict = new ArrayList<>();
        wordDict.add("aaaa");
        wordDict.add("aaa");
        solution139.wordBreak("aaaaaaa", wordDict);
    }
}
